package twentytwentyone_3;

import java.util.*;

/**
 * @Author: Zahi
 * @Description:
 * @Date Created in 2021-03-24 14:02
 * @Modified By:
 */
public class FindShortestSubArray_697 {
    public static void main(String[] args){
        int[] nums = new int[]{1, 2, 2, 3, 1};
        System.out.println(findShortestSubArray(nums));
    }

    public static int findShortestSubArray(int[] nums){
        // 为防止原数组被破坏，copy一个数组进行map处理
        int [] copy = Arrays.copyOf(nums,nums.length);
        Map<Integer, Integer> du = findDu(copy);
        int result = Integer.MAX_VALUE;
        int first = 0;
        int last = 0;
        Set<Map.Entry<Integer, Integer>> entries = du.entrySet();
        for (Map.Entry<Integer, Integer> entry : entries) {
            // 找到开始位置的下标
            for (int i = 0; i < nums.length; i++) {
                if (entry.getKey() == nums[i]){
                    first = i;
                    break;
                }
            }
            // 找到结束位置的下标
            for (int i = nums.length - 1; i > 0; i--) {
                if (entry.getKey() == nums[i]){
                    last = i;
                    break;
                }
            }
            result = Math.min((last - first + 1), result);
        }
        return result;
    }

    public static Map<Integer,Integer> findDu(int[] nums){
        // map保存  key为数字的值，value为度
        Map<Integer,Integer> map = new HashMap<>();
        int count = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == Integer.MIN_VALUE){
                continue;
            }
            int key = nums[i];
            int value = 1;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]){
                    // 避免重复
                    nums[j] = Integer.MIN_VALUE;
                    value++;
                }
            }
            // 如果value的值比count大，就说明已经找到了最大的度，清空map存入最大值
            if (value > count){
                count = value;
                map = new HashMap<>();
                map.put(key,value);
                // 如果value == count，说明有两个最大值存在，直接加入到map中
            }else if (value == count){
                map.put(key,value);
            }
        }
        return map;
    }
}
